package leetcode.N1_N100;

/**
 * @author 歪大哥😁
 * @date 2020-06-23.
 *
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 说明：你不能倾斜容器，且 n 的值至少为 2。
 *
 * 示例：
 *
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/container-with-most-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 */
public class N11 {

    /*
    用数组nums[]一次存储每条垂直线的长度
    假设桶的左右边界下表值为left,right(left < right)，可以列出面积的计算公式为：
    S = min(nums[left], nums[right]) * (right - left)
    1.假设初始left = 0,right = nums.length - 1,即选用最左和最右两条垂直线作为边界来计算，得到一个初始面积S1；
    2.若想改变面积，则必须移动垂直线的下标；
    3.无论怎么移动(right - left)变小，即上式乘号右边部分减小；
    4.如果想让乘积增大，则必须使乘号右边数值增大，即两条垂直边的短边增加，即短边向内移动一位，根据公式算出面积S2；
    5.当然如果两条边一样长，则移动哪一条都不会有影响，其实是可以两边都移动的，但是为了实现简单还是一步一步移动，只是多算了一次面积；
    6.直到两边重合，此过程中最大的S，便是容器可以容纳最多的水；
     */

    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int s = 0;
        // 一次移动一步，一共需要移动的步数
        int times = height.length - 2;
        for (int i = 0; i <= times; i++) {
            s = Math.max(s, Math.min(height[left], height[right]) * (right - left));
            if (height[left] > height[right]) {
                right--;
            } else {
                left++;
            }
        }
        return s;
    }

}
